/**
 *
 * @param n 输入
 * @returns
 */
function fib(n: number): number {
  if (n < 2) return n;
  // 1. 定义状态
  // dp保留斐波那契数列中每一个位置对应的值(状态)
  // dp[x]表示的就是x位置对应的值(状态)
  // 2. 状态转移方程: dp[i] = dp[i - 1] + dp[i - 2]
  // 状态转移方程一般情况就是写在循环(for/while)中
  // 3. 初始化状态: dp[0] = 0, dp[1] = 1初始化状态
  // 4. 计算最终的结果
  const memo: number[] = [0, 1];

  for (let i = 2; i <= n; i++) {
    if (i <= 1) {
      memo[i] = i;
      continue;
    }

    memo[i] = memo[i - 1] + memo[i - 2];
  }

  return memo[n];
}

console.log(fib(10)); // 55

export {};
